#define  _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>

using namespace std;

//回文子串
//重要的是这个算法思路将回文子串的信息放到dp表中
//时间和空间复杂度均为n^2,使用动态规划解决这个题并不是最优解，但这个思路很重要

class Solution {
public:
    int countSubstrings(string s) {
        int n = s.size();

        //创建dp表
        //初始化
        //填表
        //返回值

        vector<vector<bool>> dp(n, vector<bool>(n));

        int ret = 0;
        for (int i = n - 1; i >= 0; i--)
        {
            for (int j = i; j < n; j++)
            {
                if (s[i] == s[j]) dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;
                if (dp[i][j]) ret++;
            }

        }
        return ret;


    }
};


int main()
{
	return 0;
}